In the last decade, network coding has attracted a lot of interest. The advantages of network coding include improved throughput, robustness, scalability, and security. The performance gains are achieved by combining algebraically the packets at sources and/or at intermediate nodes in the network.
Network coding was first introduced in the seminal paper by R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, Network information flow, IEEE Transactions on Information Theory, 46(4):1204-1216, 2000. Both linear network coding, LNC, and random linear network coding, RLNC, achieve capacity when the field size is sufficiently large. However, performing operations in large finite fields is costly and complex.
RLNC in higher fields can be several orders of magnitude more energy demanding and up to one order of magnitude slower than the encoding done by simple XOR operations. This has been reported in, for example, H. Shojania and B. Li, Random network coding on the iphone: fact or fiction?, NOSSDAV, 2009; M. V. Pedersen, F. H. P. Fitzek, and T. Larsen, Implementation and performance evaluation of network coding for cooperative mobile devices, In Proc. IEEE Cognitive and Cooperative Wireless Networks Workshop, 2008; and P. Vingelmann, M. V. Pedersen, F. H. P. Fitzek, and J. Heide, Multimedia distribution using network coding on the iphone platform, Proceedings of the 2010 ACM multimedia workshop on Mobile cloud media computing, 2010. Some of the limitations of RLNC may therefore be overcome by implementing network coding only by XOR operations.
Usually randomized strategies are used for generating network codes, and not many structured strategies are known. The known structured approaches to network coding are mostly based on combinatorial design theory. Combinatorial design theory is an area of combinatorial mathematics with many communications applications. Sending linear combinations of packets instead of uncoded data offers security against eavesdropping attacks. In N. Cai and R. W. Yeung, Secure network coding, In IEEE International Symposium on Information Theory, page 323, 2002; the authors incorporate network coding and information security based on Shamir's secret sharing algorithm. The authors in K. Harada and H. Yamamoto, Strongly secure linear network coding, IEICE Transactions, 91-A(10):2720-2728, 2008; present an algorithm on how to construct a strongly k-secure network code and how to transform a nonsecure linear network code to a strongly k-secure network code if the alphabet size is sufficiently large. Although there are codes that can empower security in coded networks, the big alphabet size of these coding approaches is not desirable.
Erasure codes are becoming increasingly preferable for packet switching communications since they allow efficient recovery from packet losses. Another important application for erasure codes is in storage systems. The data storage requirements of a large storage system may be hundreds of exabytes, or even a plurality of zettabytes. For such storage systems, erasure codes are preferably used in order to tolerate and recover efficiently from multiple disk failures.
According to the rate of redundancy that is used, erasure codes are divided in two classes: 1. Optimal or very close to optimal ones, known as Maximum Distance Separable, MDS, Codes, almost-MDS, AMDS, and near-MDS codes, NMDS, and 2: Suboptimal or non-MDS codes. Reed-Solomon codes are a well known class of MDS codes that provide a general technique for construction of MDS codes. However, these codes are defined in high finite fields and they are dense codes, i.e. there are many operations in the high field and this leads to high computational complexity.
Raptor codes, as disclosed in A. Shokrollahi and M. Luby, “Raptor codes,” Foundations and Trends in Communications and Information Theory, vol. 6, no. 3-4, pp. 213-322, May 2011, form another type of erasure codes. They are rate-less codes as they can (in theory) produce an infinite number of encoding symbols. Two versions exist: Raptor, as disclosed in M. Luby, A. Shokrollahi, M. Watson, and T. Stockhammer, “Raptor Forward Error Correction Scheme for Object Delivery,” October 2007, IETF Request for Comments, RFC 5053, and RaptorQ, as disclosed in M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer, and L. Minder, “RaptorQ Forward Error Correction Scheme for Object Delivery,” IETF Request for Comments, RFC 6330 (Standards Track), August 2011. The main difference between them is that Raptor are binary codes (like LDPC), while RaptorQ are non-binary codes as they partially rely, like the Reed-Solomon codes, on operations over GF(256).
In RLNC, random linear combinations of data packets are generated over a Galois Field of size q, GF(q). The field size has an impact on the decoding probability, i.e., the probability of receiving linearly independent packets increases with q. When one or more sources want to transmit k packets to one or more destination nodes, the channel conditions must be considered. Even in a presence of packet losses (i.e. erasures) the destination node has to be able to decode k original packets by receiving k+r packets. In Daniel Enrique Lucani, Muriel Médard, and Milica Stojanovic. Random linear network coding for time-division duplexing: Field size considerations, GLOBECOM, pages 1-6. IEEE, 2009, the authors derive the average number of received coded packets n for successful decoding of k original packets at the destination nodes. They study the effect of q on the performance of RLNC and the probability that k out of k+r received packets are linearly independent. The paper shows that q equal to 4 or 8 is enough to get very close to optimal performance even when k is not very large.
However, working in high fields or with a large number of data packets increases the computational complexity and therefore increases energy consumption. RLNC in high fields is therefore not suitable for implementation on devices that have power and memory constraints.
Accordingly, a number of problems are experienced by known approaches to generating coded data packets.